<Query Kind="Statements" />


public static class MyExtension
{
    internal static IEnumerable<T> BuildTree<T>(IEnumerable<T> source, T parent) where T : ITreeEntity<T>
    {
        // 创建一个字典，用于快速查找节点的子节点
        var childrenLookup = new Dictionary<string, List<T>>();
        var list = source as ICollection<T> ?? [.. source];
        foreach (var item in list.Where(item => !childrenLookup.ContainsKey(item.Id)))
            childrenLookup[item.Id] = [];

        // 构建树结构
        foreach (var item in list.Where(item => !string.IsNullOrEmpty(item.ParentId) && childrenLookup.ContainsKey(item.ParentId)))
            childrenLookup[item.ParentId].Add(item);

        // 找到根节点，即没有父节点的节点
        foreach (var root in list.Where(x => x.Id == parent.Id))
        {
            // 为根节点和所有子节点设置Children属性
            // 使用队列来模拟递归过程
            var queue = new Queue<T>();
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                // 出队当前节点
                var current = queue.Dequeue();

                // 为当前节点设置子节点
                if (childrenLookup.TryGetValue(current.Id, out var children))
                {
                    current.Children = children;
                    foreach (var child in children)
                    {
                        // 如果子节点实现了ITreeParent接口，则设置其Parent属性
                        if (child is ITreeParent<T> tree)
                            tree.Parent = current;

                        // 将子节点入队以继续处理
                        queue.Enqueue(child);
                    }
                }
            }

            yield return root;
        }
    }
}

internal class MyClass2 : ITree<MyClass2>, ITreeEntity<MyClass2>
{
    /// <summary>
    /// 父节点
    /// </summary>
    public MyClass2 Parent { get; set; }

    /// <summary>
    /// 子级
    /// </summary>
    public ICollection<MyClass2> Children { get; set; }

    /// <summary>
    /// 名字
    /// </summary>
    public string Name { get; set; }

    /// <summary>
    /// 主键id
    /// </summary>
    public string Id { get; set; }

    /// <summary>
    /// 父级id
    /// </summary>
    public string ParentId { get; set; }
}

public interface ITree<T> : ITreeParent<T>, ITreeChildren<T>
{
    string Name { get; set; }
}

public interface ITreeParent<T>
{
    T Parent { get; set; }
}

public interface ITreeChildren<T>
{
    ICollection<T> Children { get; set; }
}

public interface ITreeEntity<T, TKey> : ITreeChildren<T> where TKey : struct, IComparable
{
    public TKey Id { get; set; }

    public TKey? ParentId { get; set; }
}

public interface ITreeEntity<T> : ITreeChildren<T>
{
    public string Id { get; set; }

    public string ParentId { get; set; }
}


public static class TreeConverter
{
    /// <summary>
    /// 将List转换为树形结构（适用于泛型Id类型）
    /// </summary>
    public static List<T> ToTree<T, TKey>(this IEnumerable<T> list)
        where T : class, ITreeEntity<T, TKey>
        where TKey : struct, IComparable
    {
        if (list == null)
            throw new ArgumentNullException(nameof(list));

        // 将所有节点放入字典便于查找
        var nodeDict = list.ToDictionary(node => node.Id);

        // 初始化所有节点的Children集合（避免null引用）
        foreach (var node in list)
        {
            node.Children ??= new List<T>();
        }

        var rootNodes = new List<T>();

        foreach (var node in list)
        {
            // 没有父节点的是根节点
            if (!node.ParentId.HasValue)
            {
                rootNodes.Add(node);
            }
            // 有父节点且能找到对应的父节点
            else if (nodeDict.TryGetValue(node.ParentId.Value, out var parent))
            {
                parent.Children.Add(node);
            }
            // 处理找不到父节点的情况（可根据实际需求调整）
            else
            {
                // 这里将找不到父节点的节点视为根节点
                rootNodes.Add(node);
            }
        }

        return rootNodes;
    }

    /// <summary>
    /// 将List转换为树形结构（适用于字符串Id类型）
    /// </summary>
    public static List<T> ToTree<T>(this IEnumerable<T> list)
        where T : class, ITreeEntity<T>
    {
        if (list == null)
            throw new ArgumentNullException(nameof(list));

        // 将所有节点放入字典便于查找
        var nodeDict = list.ToDictionary(node => node.Id);

        // 初始化所有节点的Children集合（避免null引用）
        foreach (var node in list)
        {
            node.Children ??= new List<T>();
        }

        var rootNodes = new List<T>();

        foreach (var node in list)
        {
            // 父节点ID为空或不存在的是根节点
            if (string.IsNullOrEmpty(node.ParentId) || !nodeDict.TryGetValue(node.ParentId, out var parent))
            {
                rootNodes.Add(node);
            }
            // 找到父节点，添加到父节点的子节点集合
            else
            {
                parent.Children.Add(node);
            }
        }

        return rootNodes;
    }
}

